1. Field Of The Invention
The present invention relates generally to securing communications using cryptography. More particularly, the present invention provides a method and system for enhancing the security of communications using asymmetric crypto-keys and is especially useful in enhancing communication security in conventional Kerberos authentication systems.
2. Description of the Related Art
Cryptosystems have been developed for maintaining the privacy of information transmitted across a communications channel. Often, a symmetric cryptosystem is used for this purpose. Symmetric cryptosystems, which utilize electronic keys, can be likened to a physical security system where a box has a single locking mechanism with a single key hole. One key holder uses his/her key to open the box, place a message in the box and relock the box. Only a second holder of the identical copy of the key can unlock the box and retrieve the message. The term symmetric reflects the fact that both users must have identical keys.
In more technical terms, a symmetric cryptosystem comprises an encryption function E, a decryption function D, and a shared secret-key, K. The key is a unique string of data bits to which the functions are applied. Two examples of encipherment/decipherment functions are the National Bureau of Standards Data Encryption Standard (DES) and the more recent Fast Encipherment Algorithm (FEAL). To transmit a message, M, in privacy, the sender computes C=E (M,K), where C is referred to as the ciphertext. Upon receipt of C, the recipient computes M =D (C,K), to recover the message M. An eavesdropper who copies C, but does not know K, will find it practically impossible to recover M. Typically, all details of the enciphering and deciphering functions, E and D, are well known, and the security of the system depends solely on maintaining the secrecy of key, K. Conventional symmetric cryptosystems are fairly efficient and can be used for encryption at fairly high data rates, especially if appropriate hardware implementations are used.
Asymmetric cryptosystems, often referred to as public key cryptosystems, provide another means of encrypting information. Such systems differ from symmetric systems in that, in terms of physical analogue, the box has one lock with two non-identical keys associated with it. For example, in an RSA system, either key can be used to unlock the box to retrieve a message which has been locked in the box by the other key. However, the system could be limited to using the keys in a particular sequence, such that the box can only be locked with the one key and unlocked with the other key.
In public key electronic cryptosystems, each entity, has a private key, d, which is known only to the entity, and a public key, eN, which is publicly known. Once a message is encrypted with a user's public-key, it can only be decrypted using that user's private-key, and conversely, if a message is encrypted with a user's private-key, it can only be decrypted using that user's public-key. It will be understood by those familiar with the art that although the terms "encrypt" and "decrypt" and derivations thereof are used herein in describing the use of public and private keys in an asymmetric public key cryptosystem, the term "transform" is commonly used in the art interchangeably with the term "encrypt" and the term "invert" is commonly used in the art interchangeably with the term "decrypt". Accordingly, as used herein in describing the use of public and private keys, the term "transform" could be substituted for the term "encrypt" and the term "invert" could be substituted for the term "decrypt".
If sender x wishes to send a message to receiver y, then x, "looks-up" y's public key eN, and computes M=E(C,e.sub.y) and sends it to y. User y can recover M using its private-key d.sub.y, by computing C=D(M,d.sub.y). An adversary who makes a copy of C, but does not have d.sub.y, cannot recover M. However, public-key cryptosystems are inefficient for large messages.
Public-key cryptosystems are quite useful for digital signatures. The signer, x, computes S=E(M,d.sub.x) and sends [M,S] to y. User y "looks-up" x's public-key e.sub.x, and then checks to see if M=D(S,e.sub.x). If it does, then y can be confident that x signed the message, since computing S, such that M=D(S,e.sub.x), requires knowledge of d.sub.x, x's private key, which only x knows.
Public-key cryptography also provides a convenient way of performing session key exchange, after which the key that was exchanged can be used for encrypting messages during the course of a particular communications session and then destroyed, though this can vary depending on the application.
One public key cryptographic system is the Rivest, Shamir, Adleman (RSA) system, as described in Rivest, Shamir and Adleman, "A Method of Obtaining Digital Signatures and Public Key Cryptosystems", CACM, Vol 21, pp 120-126, February 1978. RSA is a public-key based cryptosystem that is believed to be very difficult to break. In the RSA system the pair (e.sub.i N.sub.i), is user i's public-key and d.sub.i is the user's private key. Here N.sub.i =pq, where p and q are large primes. Here also e.sub.i d.sub.i =1mod.phi.(N.sub.i), where .phi.(N.sub.i)=(p-1)(q-1) which is the Euler Toitient function which returns the number of positive numbers less than N.sub.i, that are relatively prime to N.sub.i. A Carmichael function is sometime is used in lieu of a Euler Toitient function.
To encrypt a message being sent to user j, user i will compute C=M.sup.(e.sbsp.j.sup.) modN.sub.j and send C to user j. User j can then perform M=C.sup.(d.sbsp.j.sup.) modN.sub.j to recover M. User i could also send the message using his signature. The RSA based signature of user i on the message, M, is M.sup.d.sbsp.i modN.sub.i. The recipient of the message, user j, can perform (M.sup.(d.sbsp.i.sup.) modN.sub.i).sup.(e.sbsp.i.sup.) modN.sub.i, to verify the signature of i on M.
In a typical mode of operation, i sends j, M.sup.(d.sbsp.i.sup.) modN.sub.i along with M and a certificate C=(i,e.sub.i N.sub.i)(.sup.d.sbsp.CA)modN.sub.CA, where C is generated by a Certificate Authority (CA) which serves as a trusted off-line intermediary. User j can recover i's public key from C, by performing C.sup.(e.sbsp.CA.sup.) modN.sub.CA, as e.sub.CA and N.sub.CA are universally known. It should also be noted that in an RSA system the encryption and signatures can be combined.
Modifications to RSA systems have been proposed to enable multi-signatures to be implemented. Such an approach is described in "Digital Multisignature", C. Boyd, Proceedings of the Inst. of Math, and its Appl. on Cryptography and Coding, 15-17 Dec. 1986. The proposed approach extends the RSA system by dividing or splitting the user private key d into two or more portions, say d.sub.a and d.sub.b, where d.sub.a *d.sub.b =d.
"A Secure Joint Signature and Key Exchange System", Bellcore Technical Document see also U.S. patent application Ser. No. 08/277,808, which is also assigned to the assignee of the present application, modified Boyd's system, and made four significant additional points regarding split private key asymmetric cryptosystems. Although specifically applied to the two party case, the findings can be utilized more generally. The first point is that, assuming all operations are modulo N, breaking the joint signature system is equivalent to breaking RSA. This is true whether the attacker is an active or passive eavesdropper or one of the system users. It is assumed that key generation is conducted by a trusted third party, for example a tamper proof chip, and the factors of the RSA modulus N and .phi.(N) are discarded after key generation and not known to any of the system users. The second point is the description of the following key exchange protocol: User 1 sends c.sub.1 =m.sub.1.sup.d.sbsp.1 to User 2. User 2 recovers m.sub.1 =c.sub.1.sup.2.sbsp.2.sup.e. Similarly User 2 transmits m.sub.2 to User 1. Each user then computes m=.function.(m.sub.1, m.sub.2), where .function. is a function like XOR. Page and Plant prove mathematically that breaking this scheme is equivalent to breaking RSA. Again this is true whether the attacker is an active or passive eavesdropper or one of the system users. The third point is the introduction of the concept that one of the two users is a central server which maintains one portion of every user's RSA private key. In order to sign a message the user must interact with this server which, it is shown, cannot impersonate the user. Having to interact with such a central server has several important practical advantages, including instant revocation without difficult to maintain Certificate Revocation Lists (CRL), Kent, S., "Privacy Enhancement for Internet Electronic Mail: Part II: certificate Based Key Management", INTERNET RFC 1422, February 1993, a central point for audit and, as discussed below, a method of providing for digital signatures in an era where smart cards are not yet ubiquitous. Finally, the paper also proves mathematically that even if one of the two portions, d.sub.1, and d.sub.2, of the private key, d is short, say 64 bits, an eavesdropper will have equal difficulty breaking the split key system as would be experienced in breaking RSA. As a consequence, a digital signature infrastructure can be built where users who remember short (8-9 characters) passwords, can interact with the central server to create RSA signatures which are indistinguishable from those created using a full size private key stored on a smart card.
One symmetric cryptosystem is the Kerberos authentication system, Kohl, J. T. and B. C. Neuman, "The Kerberos Network Authentication Service", INTERNET RFC 1510, September 1993, which is based on the classic Needham-Schroeder authentication protocols, Needham, R. M. and Schroeder M. D., "Using Encryption for Authentication in Large Networks of Computers", Communications of the ACM, v. 21, n. 12, December 1978, with extensions by Denning-Sacco, D. E. Denning and G. M. Sacco, "Timestamps in Key Distribution Protocols," Communications of the ACM, v. 24, n. 8, August 81, pp. 553-536. The system uses a trusted third party model to perform authentication and key exchange between entities in a networked environment, for example, over a local or wide area network. Kerberos uses symmetric key cryptosystems as a primitive, and initial implementations use the Data Encryption Standard (DES) as an interoperability standard, though any other symmetric encryption standard can be used. After close to a decade of effort, the Kerberos authentication system is now a fairly mature system whose security properties have held up fairly well to intense scrutiny. Further, vendors are now delivering Kerberos as a supported product. Kerberos has also been adopted as the basis for the security service by the Open Software Foundation's (OSF) Distributed Computing Environment (DCE). Consequently, Kerberos can be expected to be among the most widespread security systems used in distributed environments over the next several years.
For the sake of clarity, a "simplified" version of the Kerberos protocol described by Neuman and Ts'o in Neuman, B. C. and Ts'o, T., "Kerberos: An Authentication Service for Computer Networks", IEEE Communications, September 1994, will be discussed below. The complete protocol is described in Kohl, J. T. and Neuman, B. C., "The Kerberos Network Authentication Service", INTERNET RFC 1510, September 1993. Further, the following discussion is based on Neuman, B. C. and Ts'o, T., "Kerberos: An Authentication Service for Computer Networks", IEEE Communications, September 1994, and for the sake of consistency uses almost the same notation. The fundamental message exchanges are shown in FIG. 1. In message 1 the user uses a personal computer or workstation 10 to request a ticket granting ticket (TGT) from an authentication server (AS) 20. The server 20 creates such a ticket TGT, looks up the user's password from the Kerberos database 30, encrypts the TGT with the password and sends it to the user via the computer 10 in message 2. The user decrypts the TGT with her password using computer 10, and stores the TGT on computer 10, for example on a hard disk or in the random access memory (RAM). Then, when the user desires to access a service, she sends message 3, which contains the TGT to the ticket granting server 40. The server 40 verifies the TGT and sends back, in message 4, a service ticket to access the service server 50, and a session key, encrypted with the user's password retrieved from database 30. In message 5 the user presents via computer 10 the service ticket to the server 50, which verifies it and also recovers the session key from it. If mutual authentication is required, the server 50, in message 6, sends back a message encrypted with the session key. All communications between servers 20, 40 and 50 and computer 10 are via network 60. All communications between servers 20 and 40 and database 30 are preferably by direct communications link.
The Kerberos messages will now be described in further detail. Message 1 known as as.sub.-- req (request to authentication service), consists of: EQU as.sub.-- req: c,tgs,time-exp, n (1)
where c is the name of the client (user), and tgs is the name of the ticket granting service associated with server 50, for which the client is requesting a ticket granting ticket and time-exp is the requested expiry time of the ticket, e.g. eight hours, and n is a fresh random number. This message is sent from computer 10 in the clear, and all parts of it are visible to an eavesdropper. The authentication server 20 responds with Message 2, with EQU as.sub.-- rep: {Kc,tgs, time-exp, n, . . . } Kc,{Tc,tgs}Ktgs(2)
where Kc,tgs is the symmetric session key to be shared between the ticket granting server (tgs) 40 and the user for the lifetime of this ticket. Kc,tgs and the other information is encrypted with symmetric key Kc which is the user's password, i.e. the long term secret which is shared with the Kerberos server. Only a user who knows Kc will be able to decrypt this message to obtain Kc,tgs. The key Kc,tgs is also embedded in the ticket Tc,tgs, which in the as.sub.-- rep is encrypted using Ktgs, a long term key known only to the server 20 and the server 40. After decrypting the first part of the message on computer 10, the user stores the data received in the as.sub.-- rep on computer 10. The main purpose of this process is to avoid storing the long term key Kc on the computer 10 where it may be compromised. Rather, the key Kc,tgs is used in subsequent communications in lieu of Kc. Since Kc,tgs is relatively short lived, the damage an attacker can cause by learning this key is significantly less than the damage which might be caused by compromise of long term key Kc. It is worth observing that the server 20 does not verify the identity of the user before responding to a user's as.sub.-- req with a as.sub.-- rep. Rather server 20 relies on the fact that to be able to make any use of the as.sub.-- rep, the recipient must know Kc. So not only can an attacker eavesdrop on the network to recover as.sub.-- rep, but can actually get an as.sub.-- rep from the server 20 by sending a fraudulent as.sub.-- req. The attacker can then take the portion of the as.sub.-- rep encrypted with Kc, and attempt to decrypt by taking guesses at Kc. Since Kc is typically a user selected password, Kc may well be a poor password, which the attacker can guess.
When the client wishes to obtain a ticket to access server 50, it sends to the server 40, Message 3, EQU tgs.sub.-- req: s, time-exp, n, {Tc,tgs}Ktgs, {ts . . . }Kc,tgs(3)
This message consists of the name of the server 50, s, the requested expiry time, time,exp, and the random number n, in clear text. It also contains the encrypted ticket granting ticket {Tc,tgs}Ktgs which was received by the client computer 10 in the as.sub.-- rep message. The server 40, which knows Ktgs, can decrypt and recover Tc,tgs, which is a valid ticket. In order to prevent a replay attack in which an attacker might gain some benefit by resending a valid {Tc,tgs}Ktgs at a later time, the tgs.sub.-- req message also contains an authenticator, which is a time stamp, ts, a check sum and other data, all encrypted with the session key Kc,tgs. Since this session key is embedded in the ticket Tc,tgs, which the server 40 has recovered, the server 40 can decrypt the authenticator and verify the time stamp and check sum, etc. By maintaining a cache of recently received authenticators, the server 40 can detect replays.
Having verified the authenticity of the tgs.sub.-- req, the server 40 responds with Message 4, EQU tgs.sub.-- rep: {Kc,s, time-exp, n, s, . . . }Kc,tgs, {Tc,s}Ks(4)
This message is very similar in structure and purpose to the as.sub.-- rep, message. The first part consists of a session key, expiry time, etc., encrypted with Kc,tgs. The client computer 10 can decrypt this to recover the session key and other information. The second portion is a ticket to access the server 50, encrypted with the long term key Ks shared by the server 50 and the server 40. The client using computer 10 now constructs Message 5 and sends it to the server 50, as follows: EQU ap.sub.-- req: {ts,ck, . . . }Kc,s {Tc,s}Ks (5)
This message is similar to the tgs.sub.-- req, in that it contains an encrypted ticket {Tc,s}Ks which the server 50 can use to recover Tc,s, which authenticates the client to the server 50 and, among other information, contains the session key Kc,s. The server 50 then uses Kc,s to decrypt the first part of the message, the authenticator, which has a time-stamp, ts, a check-sum, ck, etc.
Having verified the authenticity of the client, the client computer 10 and server 50 are ready to communicate. However, in some cases the client may request mutual authentication, in which case the server 50 must first respond with message 6, EQU ap.sub.-- rep: {ts}Kc,s (6)
which is basically proof that the server 50 successfully recovered Kc,s from the ticket Tc,s, which means the server knew Ks, which in turn is proof of authenticity of the server. The actual protocol has a number of options and is more complex, but the basic structure is defined by these six messages. Those interested are referred to Kohl, J. T. and B. C. Neuman, "The Kerberos Network Authentication Service", INTERNET RFC 1510, September 1993, for more details.
Kerberos does have limitations, and among the more serious ones are (i) compromise of the central trusted on-line Kerberos server, or the central Kerberos database, is catastrophic, since it retains long term user secrets, (ii) Kerberos is vulnerable to password guessing dictionary attacks, and (iii) Kerberos does not provide non-repudiation services, i.e. digital signatures. The first limitation is intrinsic to the Needham Schroeder protocol when used with symmetric cryptosystems like DES. The second problem is significant because experience suggests that password guessing attacks tend to be far more common than most other forms of attacks, since they are simple and effective. Finally, Kerberos was designed to provide authentication and key-exchange, but it was not designed to provide digital signatures. However, organizations using Kerberos may also need to implement digital signatures, and must now maintain separate security infrastructures for conventional Kerberos and for digital signatures, which accordingly results in significant additional costs.
Digital Equipment Corporation's SPX system, Tardo, J., and K. Alagappan, "SPX Global Authentication Using Public-Key Certificates", Proceedings of the 1991 IEEE Symposium on Research in Security and Privacy, 1991, is an example of a system with a public key infrastructure which achieves many of the same goals as Kerberos without its associated limitations. However, the SPX system does not maintain the standard Kerberos authentication system whose security properties have been widely examined. Therefore the SPX system is substantially different than the Kerberos protocol and the Kerberos source tree. In particular, the SPX system's protocol is sufficiently different from Kerberos to make integration of these systems require a complete reworking of the Kerberos protocol.
Bellovin and Merritt's Encrypted Key Exchange (EKE), Bellovin, S. M. and M. Merritt, "Encrypted Key Exchange: Password-Based Protocols Secure Against Dictionary Attacks", Proceedings of the 1992 IEEE Computer Society Conference on Research in Security and Privacy, 1992, can potentially be integrated with Kerberos to prevent dictionary attacks. However, the EKE multi-pass protocol would require very significant changes to the Kerberos system. EKE assumes that the participants share a common long term secret.
It has been suggested, by at least one expert, Kohl, J. T., "The Evolution of the Kerberos Authentication Service", EurOpen Conference Proceedings, May 1991, as quoted in Schneier, B., Applied Cryptography: Protocols, Algorithms and Source Code in C, John Wiley and Sons, New York, 1994) that: "Taking advantage of public-key cryptography would require a complete reworking of the [Kerberos] protocol".
It will perhaps also be worthwhile to describe the taxonomy of dictionary type attacks on system security. Dictionary attacks are a common form of attack, and it is well-known that many systems (e.g. UNIX or Kerberos), Morris, R. and K. Thompson. "Password Security: A Case History", Communications of the ACM, 22(11), November 1979, are vulnerable, Karn, P. R. and D. C. Feldmeier, "UNIX password security--Ten years later", Advance in Cryptology--CRYPTO 89. G. Brassard (Ed.) Lecture Notes in Computer Science, Springer-Verlag, 1990, to them. However, all dictionary attacks are not alike.
There are four parameters to a dictionary attack: The first is the known plain text, S, which can take two forms. The first form is a string S1 which is known in advance to the attacker. An example of S1 is a string of zeroes. The second form is a string S2 which is not known to the attacker in advance, but which will be known when the attack is successful. An example of S2 is any string with some form of predictable redundancy, for instance, a time stamp. Another example is a number with particular, easily tested, mathematical properties, for instance, a prime, or a non-prime with no small factors. The second parameter is the ciphertext C, typically of the form F(S,k) where k is the password being sought. The third parameter is the password space P being guessed at. The attacker will take guesses p1, p2, . . . ,pN, until a pi which is equal to k is found. The fourth parameter is the function F and its inverse, assuming one exists, which are typically public information. Those skilled in the art will recognize that important distinctions exist between cases when F is an RSA or similar function rather than a DES or similar function.
These four parameters result in at least two distinct forms of dictionary attacks. The first is S1 type attacks. Here the attacker typically computes F(S1,pi) on all passwords in P until a pi where, F(S1,pi)=C is uncovered. This is the most dangerous form of attack since the attacker can (i) recompute the F(S1,pi) for all or many pi and (ii) amortize his attack against several users. UNIX is particularly vulnerable to such attacks. The second form of attack is S2 type attacks. Here the attacker is typically computing F.sup.-1 (C,pi) and hoping to find an S2 which can be recognized. The attacker cannot start computations before C is captured. Further, since C will be different for each instance, no amortizations of the attack are possible. The Kerberos system is vulnerable to this form of attack.
A need exists for a system and method of securing communications in which the compromise of a central database, such as the database in a conventional Kerberos system, will not be catastrophic to overall system security, that is the attacker will not be able to use a compromised password or crypro key to impersonate a user. A need also remains for a system and method for securing communications which is not vulnerable to dictionary attacks. A still further need exist for a system and method for securing communications which provides a way for one user to authenticate itself to another user. Yet another need exists for a system and method for securing communications which facilitates digital signatures, being placed on a message to provide for non-repudiation. Additionally needed is a system and method for securing communications which can be used to enhance security in conventional Kerberos systems with minimum changes to the standard Kerberos protocol. Another need which continues to exist is for a system and method to secure communications which is compatible with the use of "smart cards". Finally, a system and method for securing communications is needed which allows the reuse of an authentication infrastructure for digital signature, that is the same key(s) should be available for both authentication and digital signatures and only a single secure database should be required for key storage.
Additional needs which can be satisfied by, as well as other advantages and novel features of, the present invention will become apparent to those skilled in the art from this disclosure, including the following detail description, as well as by practice of the invention. While the invention is described below with reference to preferred embodiments, it should be understood that the invention is not limited thereto. Those of ordinary skill in the art having access to the teachings herein will recognize additional applications, modifications and embodiments in other fields, which are within the scope of the invention as disclosed and claimed herein and with respect to which the invention could be of significant utility.